package leetcode.LinkedList;

/**
 * @author MaoLin Wang
 * @date 2020/2/1015:21
 */
public class _19RemoveNthFromEnd {

    /**
     * 两次遍历
     * @param head
     * @param n
     * @return
     */
    public static ListNode removeNthFromEnd(ListNode head, int n) {
        if (head == null) {
            return null;
        }
        int length = getLength(head);
        if (n < 0 || n > length) {
            return null;
        }
        ListNode temp = head;
        for (int i = 0; i < (length - n-1); i++) {
            temp = temp.next;
        }
        if (length==n){
                head=head.next;
        } else {
            if (temp.next.next != null) {

                temp.next = temp.next.next;
            } else {
                temp.next = null;
            }

        }
        return head;

    }

    /**
     * 使用 temp 节点而不直接使用 head 作为起始节点的原因是为了解决删除的是 head 节点
     * @param head
     * @param n
     */
    public static ListNode removeNthFromEndTest(ListNode head, int n) {
        if (head==null){
            return null;
        }
        if (head.next==null&&n==1){
            return null;
        }
        ListNode temp=new ListNode(-1);
        temp.next=head;
        ListNode fast=temp;
        ListNode slow=temp;
        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }
        while (fast!=null&&fast.next!=null){
            fast=fast.next;
            slow=slow.next;
        }
        slow.next=slow.next.next;
        return temp.next;
    }

    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head==null){
            return  head;
        }
        ListNode dummy = new ListNode(-1);
        dummy.next=head;
        ListNode n1 = findNFromEnd(dummy,n+1);
        n1.next=n1.next.next;
        return dummy.next;
    }

    private ListNode findNFromEnd(ListNode node, int n) {
        ListNode slow=node;
        ListNode fast=node;
        for (int i = 0; i < n; i++) {
            fast=fast.next;
        }
        while (fast!=null){
            fast=fast.next;
            slow=slow.next;
        }
        return slow;
    }


    public static int getLength(ListNode head) {
        int length = 0;
        ListNode temp = head;
        while (temp != null) {
            length++;
            temp = temp.next;
        }
        return length;
    }

    public static void main(String[] args) {
        ListNode head = new ListNode(1);
        head.next = new ListNode(2);
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = new ListNode(5);
        head.next.next.next.next.next = new ListNode(6);
        ListNode listNode = removeNthFromEndTest(head, 2);
        ListNode.printNode(listNode);
    }
}
